import collections
import heapq


# class Solution(object):
#     def maxSlidingWindow(self, nums, k):
#         """
#         :type nums: List[int]
#         :type k: int
#         :rtype: List[int]
#         """
#         n = len(nums)
#         heap = collections.deque(nums[: k])
#         index_num = {key: key for key in range(k)}
#         return_list = [0] * (n - (k - 1))
#
#         def swamp(i, j):
#             temp = index_num[i]
#             index_num[i] = index_num[j]
#             index_num[j] = temp
#             temp = heap[i]
#             heap[i] = heap[j]
#             heap[j] = temp
#
#         def build(i, m):
#             left = 2 * i + 1
#             right = 2 * i + 2
#             largest = i
#             if left < m and heap[largest] < heap[left]:
#                 largest = left
#             if right < m and heap[largest] < heap[right]:
#                 largest = right
#             if largest != i:
#                 swamp(largest, i)
#                 build(largest, m)
#
#         for i in range(k // 2 - 1, -1, -1):
#             build(i, k)
#         return_list[0] = heap[0]
#
#         for i in range(1, n - (k - 1)):
#             if nums[i + k - 1] >= heap[0]:
#                 heap.popleft()
#                 heap.appendleft(nums[i + k - 1])
#                 index_num[0] = i + k - 1
#                 return_list[i] = heap[0]
#             else:
#                 heap.append(nums[i + k - 1])
#                 m = len(heap)
#                 index_num[m - 1] = i + k - 1
#                 j = m - 1
#                 p = (j + 1) // 2 - 1
#                 while heap[p] < heap[j]:
#                     swamp(p, j)
#                     j = p
#                     p = (j + 1) // 2 - 1
#                 while index_num[0] < i:
#                     heap[0] = heap.pop()
#                     m = len(heap)
#                     index_num[0] = index_num[m]
#                     build(0, m)
#                 return_list[i] = heap[0]
#         return return_list

# 基于heapq
# class Solution(object):
#     def maxSlidingWindow(self, nums, k):
#         """
#         :type nums: List[int]
#         :type k: int
#         :rtype: List[int]
#         """
#         n = len(nums)
#         out = [0] * (n - k + 1)
#         heap = [(- nums[i], i) for i in range(k)]
#         heapq.heapify(heap)
#         print(heap)
#         out[0] = - heap[0][0]
#         for j in range(1, n - k + 1):
#             heapq.heappush(heap, (- nums[j + k - 1], j + k - 1))
#             while heap[0][1] < j:
#                 heapq.heappop(heap)
#             out[j] = - heap[0][0]
#         return out

# 基于单调栈
# class Solution(object):
#     def maxSlidingWindow(self, nums, k):
#         """
#         :type nums: List[int]
#         :type k: int
#         :rtype: List[int]
#         """
#         n = len(nums)
#         out = [0] * (n - k + 1)
#         stack = collections.deque()
#         stack.append((nums[0], 0))
#         for j in range(1, k):
#             if nums[j] < stack[-1][0]:
#                 stack.append((nums[j], j))
#             else:
#                 while stack and stack[-1][0] <= nums[j]:
#                     stack.pop()
#                 stack.append((nums[j], j))
#         out[0] = stack[0][0]
#         for i in range(1, n - k + 1):
#             if nums[i + k - 1] < stack[-1][0]:
#                 stack.append((nums[i + k - 1], i + k - 1))
#             else:
#                 while stack and stack[-1][0] <= nums[i + k - 1]:
#                     stack.pop()
#                 stack.append((nums[i + k - 1], i + k - 1))
#             while stack[0][1] < i:
#                 stack.popleft()
#             out[i] = stack[0][0]
#         return out

# 稀疏表
class Solution(object):
    def maxSlidingWindow(self, nums, k):
        n = len(nums)
        preffix = [0] * n
        suffix = [0] * n
        out = [0] * (n - k + 1)
        for i in range(n):
            if i % k == 0:
                preffix[i] = nums[i]
            else:
                preffix[i] = max(preffix[i - 1], nums[i])
        r = n // k
        for m in range(r):
            for j in range(k - 1, -1, -1):
                if j % k == k - 1:
                    suffix[m * k + j] = nums[m * k + j]
                else:
                    suffix[m * k + j] = max(nums[m * k + j], suffix[m * k + j + 1])
        for i in range(n - k + 1):
            if i % k == 0:
                out[i] = suffix[i]
            else:
                out[i] = max(preffix[i + k - 1], suffix[i])
        return out






data = Solution()
nums = [1, -1]
k = 1
print(data.maxSlidingWindow(nums, k))
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(data.maxSlidingWindow(nums, k))
